package com.leetcode.根据算法进行分类.排序算法相关.归并排序;

import com.leetcode.datastructure.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2020/12/30
 * @description: 23. 合并K个升序链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */
public class C_23_合并K个升序链表 {

	/**
	 * 如果按照 合并两个链表的思路来的话，每一次比较都会很多遍。
	 * 如果按照 归并排序的 merge 思想，会比较清晰。
	 * --
	 * 这个思路是逐个进行合并的，对比排序中的思想，就像是冒泡排序。
	 * 分析时间复杂度：假设每个链表长度为n,那么k个链表，
	 * 合并第二个链表时：n+n=2n;
	 * 合并第三个链表时：2n+n=3n;
	 * 合并第k个链表时：(k-1)n+n=kn;
	 * 那么一共：(1+2+...+k)n=>O(k^2n)
	 * 这里可以更加深刻理解归并排序的优势！
	 *
	 * @param lists
	 * @return
	 */
	public ListNode mergeKLists(ListNode[] lists) {
		if (lists == null || lists.length == 0) {
			return null;
		}
		int size = lists.length;
		for (int i = 1; i < size; i++) {
			lists[i] = mergeTwoLists(lists[i - 1], lists[i]);
		}
		return lists[size - 1];
	}


	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}


		//虚拟一个哨兵节点
		ListNode guard = new ListNode(0);
		ListNode cur1 = l1;
		ListNode cur2 = l2;
		ListNode pre = guard;
		while (cur1 != null && cur2 != null) {
			if (cur1.val < cur2.val) {
				pre.next = cur1;

				cur1 = cur1.next;
			} else {
				pre.next = cur2;

				cur2 = cur2.next;
			}
			pre = pre.next;
		}

		if (cur1 == null) {
			pre.next = cur2;
		}
		if (cur2 == null) {
			pre.next = cur1;
		}
		return guard.next;
	}


	/**
	 * 通过分治的思想进行合并
	 * 第一版有点乱
	 * 而且对于 链表为空的情况判断不方便！
	 * @param lists
	 * @return
	 */
	public ListNode mergeKListsByDivideV0(ListNode[] lists) {
		if (lists == null || lists.length == 0) {
			return null;
		}
		List<ListNode> list = new ArrayList<>();
		boolean isOdd = (lists.length & 1) == 1;
		for (int i = 1; i < lists.length; i = i + 2) {
			ListNode node = mergeTwoLists(lists[i - 1], lists[i]);
			list.add(node);
		}
		if (isOdd) {
			ListNode node = mergeTwoLists(lists[lists.length - 1], list.get(list.size() - 1));
			list.set(list.size() - 1, node);
		}

		//
		while (list.size() > 1) {
			List<ListNode> tempList = new ArrayList<>();
			isOdd = (list.size() & 1) == 1;
			for (int i = 1; i < list.size(); i = i + 2) {
				ListNode node = mergeTwoLists(list.get(i - 1), list.get(i));
				tempList.add(node);
			}
			if (isOdd) {
				ListNode node = mergeTwoLists(list.get(list.size() - 1), tempList.get(tempList.size() - 1));
				//tempList.add(node);
				tempList.set(tempList.size() - 1, node);
			}
			list = tempList;
		}

		return list.size() == 0 ? null : list.get(0);
	}


	/**
	 * 类似归并排序，每一次合并都会让待合并的数量减少一半
	 * @param lists
	 * @return
	 */
	public ListNode mergeKListsByDivideV1(ListNode[] lists) {
		if (lists == null || lists.length == 0) {
			return null;
		}
		//1.过滤 node 为 null 的情况
		List<ListNode> list = new ArrayList<>();
		for (int i = 0; i < lists.length; i++) {
			if (lists[i] != null) {
				list.add(lists[i]);
			}
		}
		while (list.size() > 1) {
			List<ListNode> tempList = new ArrayList<>();
			boolean isOdd = (list.size() & 1) == 1;
			for (int i = 1; i < list.size(); i = i + 2) {
				ListNode node = mergeTwoLists(list.get(i - 1), list.get(i));
				tempList.add(node);
			}
			if (isOdd) {
				ListNode node = mergeTwoLists(list.get(list.size() - 1), tempList.get(tempList.size() - 1));
				//tempList.add(node);
				tempList.set(tempList.size() - 1, node);
			}
			list = tempList;
		}
		return list.size() == 0 ? null : list.get(0);
	}


	public static void main(String[] args) {
		C_23_合并K个升序链表 action = new C_23_合并K个升序链表();
		//临界
		//action.mergeKListsByDivideV0(new ListNode[]{null});
		action.mergeKListsByDivideV0(new ListNode[]{new ListNode(1)});


		ListNode firstHead = new ListNode(1);
		firstHead.next = new ListNode(4);
		firstHead.next.next = new ListNode(5);

		ListNode secondHead = new ListNode(1);
		secondHead.next = new ListNode(3);
		secondHead.next.next = new ListNode(4);

		ListNode thirdHead = new ListNode(2);
		thirdHead.next = new ListNode(6);
		ListNode[] list = new ListNode[]{firstHead, secondHead, thirdHead};

		action.mergeKListsByDivideV0(list);
	}


}
